package uppgift1del3;

import java.util.Random;

public final class MaxSum {
	// globala, lagrar start och slut på sekvensen
	public static int seqStart = 0;
	public static int seqEnd = -1;

	/**
	* contiguous subsequence sum algorithm.
	* seqStart and seqEnd represent the actual best sequence.
	* Version 1
	*/
	public static int maxSubSum1( int[] a ) {
		int maxSum = 0;									// 1
		for( int i = 0; i < a.length; i++ )				// 2n
			for( int j = i; j < a.length; j++ ) {		// 7n
				int thisSum = 0;						// 0
				for( int k = i; k <= j; k++ ) {			// 4n
					thisSum += a[k];					// 0
				}										// 0
				if( thisSum > maxSum ) {				// 0
					maxSum   = thisSum;					// 0
					seqStart = i;						// 0
					seqEnd   = j;						// 0
				}										// 0
			}											// 0
		return maxSum;									// 0
	}													// 0

	// Version 2
	public static int maxSubSum2( int [ ] a ) {
		int maxSum = 0;									// 1
		for( int i = 0; i < a.length; i++ ) {			// 4n
			int thisSum = 0;							// 0
			for( int j = i; j < a.length; j++ ) {		// 8n
				thisSum += a[ j ];						// 0
				if( thisSum > maxSum ) {				// 0
					maxSum = thisSum;					// 0
					seqStart = i;						// 0
					seqEnd   = j;						// 0
				}
			}
		}
		return maxSum;
	}
	
	// Version 3
	public static int maxSubSum3( int[] a ) {
		int maxSum  = 0;								// 1
		int thisSum = 0;								// 1
		for( int i = 0, j = 0; j < a.length; j++ ) {	// 12n
			thisSum += a[ j ];							// 0
			if( thisSum > maxSum ) {					// 0
				maxSum = thisSum;						// 0
				seqStart = i;							// 0
				seqEnd   = j;							// 0
			}
			else if( thisSum < 0 ) {					// 0
				i = j + 1;								// 0
				thisSum = 0;							// 0
			}
		}
		return maxSum;
	}
}

// 1+56n^3
// 1+36n^2
// 2+12n